package com.sicheng.蓝桥.练习题.dp;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/2 11:24
 */
public class 组合 {
    /**
     * 题意：给出 N（2≤N≤1e6）求满足以下条件的 X 的数量，需除以模 (998244353)
     * <p>
     * X 是 N 位数
     * 对于 X1,X2,...,XN 的每位数
     * 1≤Xi≤9
     * |Xi−Xi|≤1
     * 思路：
     * <p>
     * emm，直接看过去知道是比较明显的数论推导问题，
     * 随便写了几组发现当定义状态 fi,j 表示长度为 i 符合条件的数字，结尾数位是 j 有多少个。递推式如下：
     * <p>
     * fi,j=fi−1,j−1+fi−1,j+fi−1,j+1fi,0=fi,10=0f1,j=1
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        long mod = 998244353;
        //dp[i][j] 是i位数,以j结尾的总个数
        long[][] dp = new long[n + 1][11];

        Arrays.fill(dp[1], 0, dp[0].length, 1);

        long sum = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < 10; j++) {
                dp[i][j] = ((dp[i - 1][j - 1] + dp[i - 1][j]) % mod + dp[i - 1][j + 1]) % mod;
                sum = (sum + dp[i][j]) % mod;
            }
        }
        System.out.println((sum + 10) % 998244353);
    }
}
